Sipser CH2 PROBLEMS'ANSWER 2.43-2.50

2.43

没看懂，有待后续补充

2.44

分别为识别的DFA

构造PDA识别:

,
is start state
:
- ,
- ,
- ,
- ,

2.45

考虑,应用pumping lamma 易验证

2.46

是由多个形似的串拼接而成，考虑,有两个parse tree，故该语言ambiguous。
构造无二义的CFG关键在与消除:
证明无二义分两步：
- 证明无二义，运用归纳法
- 证明无二义，对于分解为的串，有唯一最左推导

2.47

形式化定义：

一个下推自动机可以定义为。

状态集 :
- : 初始状态，用于读取前半部分。
- : 开始读取后半部分，但尚未遇到 '1'。
- : 在中已经遇到了 '1'。
- : 接受状态。
输入字母表 :
堆栈字母表 : ( 是初始堆栈符号)
初始状态:
初始堆栈符号:
接受状态集 :
转移函数 :
1. 读取前半部分 : 在状态，每读入一个符号，就压入一个。
  - 对于任何
  - 对于任何
2. 猜测和的分割点: 非确定性地从转换到，不消耗输入。
  - 对于任何
3. 读取 (未见 '1'): 在状态，每读一个符号，弹出一个。如果读到 '1'，则进入。
4. 读取 (已见 '1'): 在状态，继续读完的剩余部分，每读一个符号弹出一个。
5. 接受: 当输入结束时，如果 PDA 处于状态（表示已在中见到'1'）并且堆栈没有因为而提前变空，则可以转换到接受状态。
  - 对于任何

这个 PDA 通过非确定性地猜测分割点，并利用堆栈来比较和的长度，同时检查中是否含有 '1'，从而正确地识别语言。

设计一个生成的上下文无关文法 (CFG)

构造 CFG 的一个有效策略是，将语言分解为几个更简单的部分，然后为每个部分编写产生式。一个字符串属于，意味着它可以表示为的形式，其中且中含有 '1'。这个长度条件可以分解为两种情况：

: 这可以通过在满足条件的字符串前添加任意字符来实现。
: 这是最基本的情况。

所以，我们可以设计一个产生核心字符串的文法，然后允许在这些字符串的左侧添加任意数量的字符。

: 在任何属于的字符串前面添加一个 '0' 或 '1'，新字符串仍然属于。因为这会使部分的长度加一，而部分保持不变，所以的条件仍然满足。
: 和是基本情况，它们生成长度关系为或的字符串。

我们定义四组产生式：

: 生成偶数长度的字符串，其中且中有 '1'。
: 生成偶数长度的字符串，其中且中只有 '0'。
: 生成奇数长度的字符串，其中且中有 '1'。
: 生成奇数长度的字符串，其中且中只有 '0'。

思路： 我们从外向内生成字符串。例如，对于生成的字符串，如果已经满足条件（属于），那么无论是什么，新的部分总是包含 '1'。如果的后半部分不包含 '1'（属于），那么我们必须确保添加的是 '1'，才能使新的字符串属于。

文法规则： 令为起始符号。

- (解释: 规则表示，如果内部字符串的后半部分有 '1'，则新字符串的后半部分也一定有 '1'。规则表示，如果内部字符串的后半部分全是 '0'，则右侧必须添加 '1'。01 | 11 是最短的（长度为2）满足条件的基本情况。)
- (解释: 要想后半部分只包含 '0'，右侧添加的必须是 '0'，并且内部字符串的后半部分也必须只包含 '0'。00 | 10 是基本情况。)
- (解释: 逻辑与类似，但处理的是奇数长度的字符串。基本情况的长度为3。)
- (解释: 逻辑与类似。基本情况的长度为3。)

这个 CFG 首先通过规则 (1) 确保了可以比任意长，然后通过规则 (2) 到 (5) 精确地生成了和的基本情况，同时保证了部分必须含有 '1'。

2.48

1. 构造PDA
- ,
- ,分别是1的前缀和后缀。
- PDA:读,向栈压一个或两个.读,弹出一个
- PDA:读,向栈压一个.读,弹出一个或两个
考虑字符

2.49

设是一个在字母表上的上下文无关语言 (CFL)。

第一步：引入标记字母表

我们创建两个与不相交的新字母表，作为的“标记”副本： * *

第二步：使用逆同态映射

定义一个同态 (homomorphism) ，如下所示： * 对于所有的，令 * 对于所有的，令

这个同态将标记过的符号映射回其原始形式。

现在，我们考虑语言。根据定义，它是：由于上下文无关语言类在逆同态操作下是封闭的，所以是一个上下文无关语言。

第三步：与正则表达式相交

考虑正则表达式。这个表达式描述了所有先由中的符号组成，后由中的符号组成的字符串。我们构造一个新语言：由于上下文无关语言类在与正则语言的交集操作下是封闭的，所以也是一个上下文无关语言。

中的每个字符串都具有以下形式： * ，其中且。 * 。

如果我们令和，那么中的每个字符串都对应于原始语言中一个字符串的一种分割方式。

第四步：交换标记部分

现在，我们定义一个新语言，它通过交换中每个字符串的两部分得到： $其中且$ 这是一个关键步骤。有一个已知的定理指出，如果是一个上下文无关语言（其中和不相交），那么语言也是上下文无关的。

根据这个定理，由于是一个 CFL，那么也是一个 CFL。

第五步：使用同态映射回原始字母表

最后，我们将语言通过同态映射回原始字母表：由于上下文无关语言类在同态操作下是封闭的，所以也是一个上下文无关语言。

我们来分析的内容。中的每个字符串都是的形式，其中。 * 。 * 根据的定义，存在和使得。 * 根据的定义，这意味着。 * 令且。那么。 * 因此，。

所以，的定义可以写为：这正是旋转闭包的定义。

2.50

考虑,

ZC's Blog